package linklist;

//判断有无环路，返回第一个节点
public class LeetCode_142 {
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    //快慢指针
    public ListNode detectCycle(ListNode head) {
        if (head == null){
            return null;
        }
        ListNode fast = head,slow = head;
        do{
            if (fast.next!=null && fast.next.next!=null){
                fast = fast.next.next;
            }else {
                return null;
            }
            slow = slow.next;
        }while (fast!=slow);
        slow = head;
        while (slow!=fast){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }




}
